package com.sunny.structure.lineartable.singlelinked;

import java.util.HashMap;

/**
 * @author Sunny
 * @date 2020/5/12
 */
public class Test2 {


    /**
     * 采用递归的方式合并两个有序链表
     */
    public static ListNode mergeTwoList(ListNode head1, ListNode head2) {
        if (head1 == null && head2 == null) {
            return null;
        }
        //当head1为null,表示head2中的剩余节点都比head1的要小,直接赋值到head的next即可
        if (head1 == null) {
            return head2;
        }
        //同上
        if (head2 == null) {
            return head1;
        }

        ListNode head;
        //选择较小值的节点作为头节点
        if (head1.value > head2.value) {
            head = head2;
            //因为head2已经作为头节点,所以从head2的下一个节点开始
            head.next = mergeTwoList(head1, head2.next);
        } else {
            head = head1;
            //同上
            head.next = mergeTwoList(head1.next, head2);
        }
        return head;
    }

    /**
     * 采用非递归的方式合并两个有序链表
     */
    public static ListNode mergeTwoList2(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        //选择较小值的头节点作为基准链表,另一个链表会合并到基准链表上
        ListNode head = head1.value < head2.value ? head1 : head2;
        //cur1指针指向头节点为较小值的链表
        ListNode cur1 = head == head1 ? head1 : head2;
        //cur2指针指向另一个链表
        ListNode cur2 = head == head1 ? head2 : head1;

        ListNode pre = null;    //cur1前一个几点
        ListNode next = null;   //cur2后一个节点
        while (cur1 != null && cur2 != null) {
            //首次肯定会进判断, 如果cur1小于等于cur2
            if (cur1.value <= cur2.value) {
                //首次pre为基准链表的头节点
                pre = cur1;                             //1     5
                //cur1向后移动
                cur1 = cur1.next;                       //5     9
            } else {
                //开始合并
                //记录cur2的next
                next = cur2.next;                       //4     8       null
                //将cur2赋值到基准节点的下一个节点
                pre.next = cur2;                        //2     4       8
                //将基准节点的当前指针指向cur2的下一个节点
                cur2.next = cur1;                       //5     5       9

                //变化指针
                pre = cur2;                             //2     4       8
                cur2 = next;                            //4     8       null
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;          //9
        return head;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(5);
        ListNode head3 = new ListNode(9);
        head1.next = head2;
        head2.next = head3;

        ListNode head4 = new ListNode(2);
        ListNode head5 = new ListNode(4);
        ListNode head6 = new ListNode(8);
        head4.next = head5;
        head5.next = head6;

//        ListNode head = mergeTwoList(head1, head4);
        ListNode head = mergeTwoList2(head1, head4);
        ListNode.traverse(head);
    }
}
